package visualizer.client.algorithms.bst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

/**
 * User: DDovzhenko
 * Date: 06.01.14
 * Time: 17:17
 */
public class BSTAddingAlgorithm implements Algorithm {
    private int totalStepCount;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        BNode newNode = new BNode(inputValue);
        newNode.setInnerColor("lightgreen");
        newNode.setOuterColor("green");
        return insertToBST(tree.copyTree(false), newNode, step);
    }

    @Override
    public int getStepsCount(BinaryTree tree, int inputValue) {
        totalStepCount = 0;
        insertToBST(tree.copyTree(false), new BNode(inputValue), -1);
        return totalStepCount;
    }

    private AlgoResult insertToBST(BinaryTree bTree, BNode newNode, int stepNo) {
        if (stepNo-- == 0) {
            return new AlgoResult(bTree, "Вставка узла с ключом " + newNode.getValue());
        }
        BNode theRootNode = bTree.getRoot();
        if (theRootNode == null) {
            bTree.setRootNode(newNode);
            if (stepNo-- == 0) {
                return new AlgoResult(bTree, "Дерево пусто, поэтому добавляем узел с ключом " + newNode.getValue() + " в корень");
            }
        } else {
            while (true) {
                if (newNode.getValue().compareTo(theRootNode.getValue()) == 0) {
                    updateTotalStepCount(stepNo);
                    return new AlgoResult(bTree, "Узел с ключом " + newNode.getValue() + " существует и не может быть добавлен");
                } else if (newNode.getValue().compareTo(theRootNode.getValue()) < 0) {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ " + newNode.getValue() + " меньше ключа " + theRootNode.getValue() + ", обрабатываем левое поддерево");
                    }
                    if (theRootNode.getLeftBNode() == null) {
                        if (stepNo-- == 0) {
                            theRootNode.setOuterColor("red");
                            return new AlgoResult(bTree, "У узла нет левого потомка, поэтому добавляем узел с ключом " + newNode.getValue());
                        }
                        theRootNode.setLeftBNode(newNode);
                        break;
                    }
                    theRootNode = theRootNode.getLeftBNode();
                } else {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ  " + newNode.getValue() + " больше ключа " + theRootNode.getValue() + ", обрабатываем правое поддерево");
                    }
                    if (theRootNode.getRightBNode() == null) {
                        if (stepNo-- == 0) {
                            theRootNode.setOuterColor("red");
                            return new AlgoResult(bTree, "У узла нет правого потомка, поэтому добавляем узел с ключом " + newNode.getValue());
                        }
                        theRootNode.setRightBNode(newNode);
                        break;
                    }
                    theRootNode = theRootNode.getRightBNode();
                }
            }
        }
        updateTotalStepCount(stepNo);
        return new AlgoResult(bTree, "Узел с ключом " + newNode.getValue() + " был успешно добавлен");
    }

    private void updateTotalStepCount(int stepNo) {
        if (stepNo < 0) {
            totalStepCount = -stepNo;
        }
    }
}
